#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

void showAll(const std::vector<std::vector<int>> &raw){
    for(int i=0;i<=int(raw.size())-1;++i){
        for(int j=0;j<=int(raw[i].size())-1;j++){
            std::cout<<raw[i][j]<<' ';
        }std::cout<<std::endl;
    }
}

class Solution {
public:
    int minDistance(std::string word1, std::string word2) {
        if(word1.empty()){
            return word2.size();
        }
        if(word2.empty()){
            return word1.size();
        }

        std::vector<std::vector<int>> board(word1.size()+1,
            std::vector<int>(word2.size()+1,0));
        const int m=board.size(), n=board[0].size();

        for(int j=0;j<=n-1;j++){
            board[0][j]=j;
        }
        for(int i=0;i<=m-1;i++){
            board[i][0]=i;
        }
        // showAll(board);
        // std::cout<<"----------\n";

        for(int i=1;i<=m-1;i++){
            for(int j=1;j<=n-1;j++){
                board[i][j]=std::min<int>(
                    board[i][j-1]+1,
                    board[i-1][j-1]+(word1[i-1]!=word2[j-1])
                );
                board[i][j]=std::min<int>(
                    board[i][j],
                    board[i-1][j]+1
                );
                
            }
        }

        // showAll(board);
        return board[m-1][n-1];   
    }
};

int main(){
    Solution test{};
    const std::string word1{"intention"};
    const std::string word2{"execution"};

    std::cout<<test.minDistance(word1,word2);
    std::cout<<"智障"<<std::endl;
    return 0;
}